{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Arrangement II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #优美的排列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>n</code> 和 <code>k</code> ，请你构造一个答案列表 <code>answer</code> ，该列表应当包含从 <code>1</code> 到 <code>n</code> 的 <code>n</code> 个不同正整数，并同时满足下述条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>假设该列表是 <code>answer = [a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ... , a<sub>n</sub>]</code> ，那么列表 <code>[|a<sub>1</sub> - a<sub>2</sub>|, |a<sub>2</sub> - a<sub>3</sub>|, |a<sub>3</sub> - a<sub>4</sub>|, ... , |a<sub>n-1</sub> - a<sub>n</sub>|]</code> 中应该有且仅有 <code>k</code> 个不同整数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回列表 <code>answer</code> 。如果存在多种答案，只需返回其中 <strong>任意一种</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 1\n",
    "<strong>输出：</strong>[1, 2, 3]\n",
    "<strong>解释：</strong>[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 2\n",
    "<strong>输出：</strong>[1, 3, 2]\n",
    "<strong>解释：</strong>[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k < n <= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-arrangement-ii](https://leetcode.cn/problems/beautiful-arrangement-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-arrangement-ii](https://leetcode.cn/problems/beautiful-arrangement-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n1', '3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [1]\n",
    "        sign = 1\n",
    "        for diff in range(k, 0, -1):\n",
    "            res.append(res[-1] + sign * diff)\n",
    "            sign = -sign\n",
    "\n",
    "        for x in range(k + 2, n + 1):\n",
    "            res.append(x)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            ans.append(i)\n",
    "            if i != j:\n",
    "                ans.append(j)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = [1]\n",
    "        flag = 1\n",
    "        for i in range(k):\n",
    "            answer.append(answer[-1]+flag*(k-i))\n",
    "            flag*=(-1)\n",
    "        return answer+list(range(k+2,n+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        i = 1\n",
    "        j = n\n",
    "        t = 0\n",
    "        for s in range(k):\n",
    "            if t == 0:\n",
    "                ans.append(i)\n",
    "                i += 1\n",
    "                t = 1\n",
    "            else:\n",
    "                ans.append(j)\n",
    "                j -= 1\n",
    "                t = 0\n",
    "        if t == 0:\n",
    "            for s in range(n-k):\n",
    "                ans.append(j)\n",
    "                j -= 1\n",
    "        else:\n",
    "            for s in range(n-k):\n",
    "                ans.append(i)\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int):\n",
    "        res = []\n",
    "        for i in range(n,k,-1):\n",
    "            res.append(i)\n",
    "        f, c = -1, k+1\n",
    "        for i in range(k,0,-1):\n",
    "            c += f * i\n",
    "            f = -f\n",
    "            res.append(c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "            # print(answer)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [0] * n\n",
    "        # res = []\n",
    "        i = 0\n",
    "        p, q = 1, n\n",
    "        for j in range(k):\n",
    "            if j % 2 == 0:\n",
    "                res[i] = p\n",
    "                # res.append(p)\n",
    "                p += 1\n",
    "            else:\n",
    "                res[i] = q\n",
    "                # res.append(q)\n",
    "                q -= 1\n",
    "            i += 1\n",
    "\n",
    "        if k % 2 == 0:\n",
    "            while i < n:\n",
    "                res[i] = q\n",
    "                q -= 1\n",
    "                i += 1\n",
    "        else:\n",
    "            while i < n:\n",
    "                res[i] = p\n",
    "                p += 1\n",
    "                i += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "# 一种满足条件的排列规律： 1, k+1, 2, k-1,...一共k + 1个，然后多余的数字从k+2...n即可\n",
    "# class Solution:\n",
    "#     def constructArray(self, n: int, k: int) -> List[int]:\n",
    "#         res = [0] * n\n",
    "#         i, j = 0, 1\n",
    "#         while i < n:\n",
    "#             res[i] = i + 1\n",
    "#             if i <= k:\n",
    "#                 if i % 2:\n",
    "#                     res[i] = k + 2 - j\n",
    "#                     j += 1\n",
    "#                 else:\n",
    "#                     res[i] = j\n",
    "#             i += 1\n",
    "#         return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def constructArray(self, n: int, k: int) -> List[int]:\n",
    "#         res = [1]\n",
    "#         sign = 1\n",
    "#         for diff in range(k, 0, -1):\n",
    "#             res.append(res[-1] + sign * diff)\n",
    "#             sign = -sign\n",
    "#         for x in range(k + 2, n + 1):\n",
    "#             res.append(x)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        i = 1\n",
    "        j = n\n",
    "        res = []\n",
    "        while i <= j:\n",
    "            if k == 1:\n",
    "                res.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                if k % 2 != 0:\n",
    "                    res.append(i)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(j)\n",
    "                    j -= 1\n",
    "                k -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        a=1\n",
    "        b=k+1\n",
    "        ans=[]\n",
    "        while a<=b:\n",
    "            if a<b:\n",
    "                ans.append(a)\n",
    "                ans.append(b)\n",
    "            elif a==b:\n",
    "                ans.append(a)\n",
    "            a+=1\n",
    "            b-=1\n",
    "        lst=[i for i in range(k+2,n+1)]\n",
    "        ans+=lst\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            ans.append(i)\n",
    "            if i != j:\n",
    "                ans.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        # 前k-1个diff交替为n-1,n-2,n-3\n",
    "        # 最后一个diff为1\n",
    "        # 也就是说前k个数字交替先排好\n",
    "        ret=[1]\n",
    "        diff=n-1\n",
    "        i=0\n",
    "        sign=1\n",
    "        while i<k-1:\n",
    "            ret.append(ret[-1]+sign*diff)\n",
    "            diff-=1\n",
    "            sign*=-1\n",
    "            i+=1\n",
    "        # 假设前面安排好的数字是偶数个，也就是说交替出现了k-1个diff\n",
    "        # 当前应该是一个大值，后续为单调减1的序列\n",
    "        while len(ret)<n:\n",
    "            if(k%2==0):\n",
    "                ret.append(ret[-1]-1)\n",
    "            else:\n",
    "                ret.append(ret[-1]+1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [1]\n",
    "        offset = 1\n",
    "        incre = -1\n",
    "        while k > 1:\n",
    "            if incre == 1:\n",
    "                res.append(offset)\n",
    "            else:\n",
    "                res.append(n + 1 - offset)\n",
    "                offset += 1\n",
    "            k -= 1\n",
    "            incre = -incre\n",
    "        while len(res) < n:\n",
    "            res.append(res[-1] - incre)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(1, n - k):\n",
    "            ans.append(i)\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            ans.append(i)\n",
    "            if (i != j):\n",
    "                ans.append(j)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        # 相邻元素差的绝对值 diff 有 k 个不同的数：\n",
    "        # 构造 diff 分别为 k, k - 1, ..., 2, 1 的数组\n",
    "\n",
    "        res = [1]\n",
    "        flag = True\n",
    "\n",
    "        for diff in range(k, 0, -1):\n",
    "            if flag:\n",
    "                res.append(res[-1] + diff)\n",
    "            else:\n",
    "                res.append(res[-1] - diff)\n",
    "\n",
    "            flag ^= True\n",
    "            \n",
    "        res += [x for x in range(k + 2, n + 1)]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        p,q=1,n\n",
    "        i=0\n",
    "        while i<k:\n",
    "            if i%2==0:\n",
    "                ans[i]=p\n",
    "                p+=1\n",
    "            else:\n",
    "                ans[i]=q\n",
    "                q-=1\n",
    "            i+=1\n",
    "        if k%2==0:\n",
    "            while i<n:\n",
    "                ans[i]=q\n",
    "                q-=1\n",
    "                i+=1\n",
    "        else:\n",
    "            while i<n:\n",
    "                ans[i]=p\n",
    "                p+=1\n",
    "                i+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(1, (k + 1) // 2 + 1):\n",
    "            ans.append(i)\n",
    "            ans.append(k + 2 - i)\n",
    "        if k % 2 == 0:\n",
    "            ans.append(1 + k // 2)\n",
    "        return ans + [i for i in range(k + 2, n + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res=[]\n",
    "        for i in range(1, n-k):\n",
    "            res.append(i)\n",
    "        i=n-k\n",
    "        j=n\n",
    "        while i<=j:\n",
    "            res.append(i)\n",
    "            if i!=j:\n",
    "                res.append(j)\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        t = n - k - 1\n",
    "        a = n - k\n",
    "        b = n\n",
    "        for i in range(t):\n",
    "            ans[i] = i + 1\n",
    "        i = t\n",
    "        while i < n:\n",
    "            ans[i] = a\n",
    "            i += 1\n",
    "            a += 1\n",
    "            if i < n:\n",
    "                ans[i] = b\n",
    "                i += 1\n",
    "                b -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        flag = 1\n",
    "        result = [1]\n",
    "        cur = k\n",
    "        while(cur > 0):\n",
    "            result.append(result[-1]+flag*cur)\n",
    "            cur -= 1\n",
    "            flag = -flag\n",
    "        result += list(range(k+2,n+1))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> list[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 一种满足条件的排列规律： 1, k+1, 2, k-1,...一共k + 1个，然后多余的数字从k+2...n即可\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [0] * n\n",
    "        i, j = 0, 1\n",
    "        while i < n:\n",
    "            res[i] = i + 1\n",
    "            if i <= k:\n",
    "                if i % 2:\n",
    "                    res[i] = k + 2 - j\n",
    "                    j += 1\n",
    "                else:\n",
    "                    res[i] = j\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def constructArray(self, n: int, k: int) -> List[int]:\n",
    "#         res = [1]\n",
    "#         sign = 1\n",
    "#         for diff in range(k, 0, -1):\n",
    "#             res.append(res[-1] + sign * diff)\n",
    "#             sign = -sign\n",
    "#         for x in range(k + 2, n + 1):\n",
    "#             res.append(x)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\r\n",
    "        ret = [1]\r\n",
    "        sign = 1\r\n",
    "        interval = k\r\n",
    "        for i in range(k):\r\n",
    "            ret.append(ret[i]+interval*sign)\r\n",
    "            sign *= -1\r\n",
    "            interval -= 1\r\n",
    "        for i in range(n-k-1):\r\n",
    "            ret.append(len(ret)+1)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [i for i in range(1,n+1)]\n",
    "        flag = -1\n",
    "        for i in range(k-1,-1,-1):\n",
    "            res[i] = res[i+1] + flag*(i+1)\n",
    "            flag = -flag\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = list(range(1, n+1))\n",
    "        interval = k\n",
    "        for i in range(1, k+1):\n",
    "            if i%2:\n",
    "                ans[i] = ans[i-1] + interval\n",
    "            else:\n",
    "                ans[i] = ans[i-1] - interval\n",
    "            interval -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(1, n-k):\n",
    "            ans.append(i)\n",
    "        for i in range(1,(k+1)//2 + 1):\n",
    "            ans.append(n-(k + 1 - i))\n",
    "            ans.append(n + 1 - i)\n",
    "        if k % 2 == 0:\n",
    "            ans.append((2*n-k)//2)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = list(range(1, n-k))\n",
    "        i, j = n - k, n\n",
    "\n",
    "        while i <= j:\n",
    "            res.append(i)\n",
    "            if i != j:\n",
    "                res.append(j)\n",
    "            i, j = i + 1, j -1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        if k%2==0:\n",
    "            k=k//2\n",
    "            res = [0]*(n)\n",
    "            num = n\n",
    "            for i in range(k):\n",
    "                res[i*2] = num\n",
    "                num-=1\n",
    "            num = 1\n",
    "            for i in range(n):\n",
    "                if res[i]==0:\n",
    "                    res[i] = num\n",
    "                    num+=1\n",
    "            \n",
    "        else:\n",
    "            k=k//2\n",
    "            res = [0]*(n)\n",
    "            num = n\n",
    "            for i in range(k):\n",
    "                res[i*2+1] = num\n",
    "                num-=1\n",
    "            num = 1\n",
    "            for i in range(n):\n",
    "                if res[i]==0:\n",
    "                    res[i] = num\n",
    "                    num+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        flag = 1\n",
    "        result = [1]\n",
    "        cur = k\n",
    "        while(cur > 0):\n",
    "            result.append(result[-1]+flag*cur)\n",
    "            cur -= 1\n",
    "            flag = -flag\n",
    "        result += list(range(k+2,n+1))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = [0] * n\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        p, q = 1, n \n",
    "\n",
    "        for j in range(k):\n",
    "            if j % 2 == 0:\n",
    "                ans[i] = p\n",
    "                p += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                ans[i] = q\n",
    "                q -= 1\n",
    "                i += 1\n",
    "\n",
    "        if k % 2 == 0:\n",
    "            while(i < n):\n",
    "                ans[i] = q\n",
    "                q -= 1\n",
    "                i += 1\n",
    "        else:\n",
    "            while(i < n):\n",
    "                ans[i] = p\n",
    "                p += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        i, j = 1, k + 1\n",
    "        f = 0\n",
    "        while len(ans) < k + 1:\n",
    "            if f:\n",
    "                ans.append(j)\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans.append(i)\n",
    "                i += 1\n",
    "            f ^= 1\n",
    "\n",
    "        k += 2\n",
    "        while k <= n:\n",
    "            ans.append(k)\n",
    "            k += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "'''\n",
    "1 2 3 4 5 6 -1\n",
    "2 1 3 4 5 6 -2\n",
    "1 4 2 3 5 6 -3\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\r\n",
    "        mid=n-k\r\n",
    "        ret=list(range(1,mid))\r\n",
    "        i,j=mid,n\r\n",
    "        while i<=j:\r\n",
    "            if i==j:\r\n",
    "                ret.append(i)\r\n",
    "                break\r\n",
    "            ret.append(i)\r\n",
    "            ret.append(j)\r\n",
    "            i+=1\r\n",
    "            j-=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        even, odd = 1, n\n",
    "        res = [0] * n\n",
    "        for i in range(k):\n",
    "            if i % 2 == 0:\n",
    "                res[i] = even\n",
    "                even += 1\n",
    "            else:\n",
    "                res[i] = odd\n",
    "                odd -= 1\n",
    "\n",
    "        i += 1\n",
    "        while i < n:\n",
    "            if k % 2 == 0:\n",
    "                res[i] = odd\n",
    "                odd -= 1\n",
    "            else:\n",
    "                res[i] = even\n",
    "                even += 1\n",
    "            i += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        a=1\n",
    "        b=k+1\n",
    "        ans=[]\n",
    "        while a<=b:\n",
    "            if a<b:\n",
    "                ans.append(a)\n",
    "                ans.append(b)\n",
    "            elif a==b:\n",
    "                ans.append(a)\n",
    "            a+=1\n",
    "            b-=1\n",
    "        lst=[i for i in range(k+2,n+1)]\n",
    "        ans+=lst\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        观察：\n",
    "            [1,2,3,4,5] -> [1,5,2,4,3] 共4个不同数\n",
    "            [1,2,3,4,5,6] -> [1,6,2,5,3,4] 共5个不同数\n",
    "        因此，1到n个数最多可生成n-1个不同的数\n",
    "        \"\"\"\n",
    "\n",
    "        ans = []\n",
    "        i, j = k+1, 1\n",
    "        while i > j:\n",
    "            ans.append(j)\n",
    "            ans.append(i)\n",
    "            i -= 1\n",
    "            j += 1\n",
    "        if i == j:\n",
    "            ans.append(i)\n",
    "        ans.extend(range(k+2,n+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "            [1, 2, ..., m, n, m+1, n-1, ..., ]\n",
    "\n",
    "\n",
    "            # m 个 1, n-m-1 个不是 1 \n",
    "            # n - m 个不同的数\n",
    "            [1, 1, ..., 1, n-m, n-m-1, n-m-2, 1]\n",
    "        \"\"\"\n",
    "        m = n - k\n",
    "        res = []\n",
    "        for i in range(1, m+1):\n",
    "            res.append(i)\n",
    "        \n",
    "        left, right = m+1, n\n",
    "\n",
    "        for i in range(n - m):\n",
    "            if i % 2 == 0:\n",
    "                res.append(right)\n",
    "                right -= 1\n",
    "            else:\n",
    "                res.append(left)\n",
    "                left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        # 相邻元素差的绝对值 diff 有 k 个不同的数：\n",
    "        # 构造 diff 分别为 k, k - 1, ..., 2, 1 的数组\n",
    "\n",
    "        res = [1]\n",
    "        sign = 1\n",
    "\n",
    "        for diff in range(k, 0, -1):\n",
    "            res.append(res[-1] + sign * diff)\n",
    "            sign = -sign\n",
    "            \n",
    "        res += [x for x in range(k + 2, n + 1)]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = []\n",
    "        a = 1\n",
    "        m = k + 1\n",
    "        for i in range(1, k + 2):\n",
    "            if i % 2 == 1:\n",
    "                ans.append(a)\n",
    "                a += 1\n",
    "            else:\n",
    "                ans.append(m)\n",
    "                m -= 1\n",
    "\n",
    "        for i in range(1 + k + 1, n + 1):\n",
    "            ans.append(i)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        ans = [1]\n",
    "        candidate = [i for i in range(1, n + 1)]\n",
    "        pre, end = 1, n - 1\n",
    "        flag = True\n",
    "        while k > 1 and end > pre:\n",
    "            if flag == True:\n",
    "                ans.append(candidate[end])\n",
    "                end -= 1\n",
    "            else:\n",
    "                ans.append(candidate[pre])\n",
    "                pre += 1\n",
    "            flag = not flag\n",
    "            k -= 1\n",
    "        if abs(candidate[end] - ans[-1]) == 1:\n",
    "            for i in range(end, pre - 1, -1):\n",
    "                ans.append(candidate[i])\n",
    "        else:\n",
    "            for i in range(pre, end + 1):\n",
    "                ans.append(candidate[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        result = list(range(1, n-k))\n",
    "        i, j = n-k, n\n",
    "        while i <= j:\n",
    "            result.append(i)\n",
    "            if i != j:\n",
    "                result.append(j)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return result\n",
    "\n",
    "    def constructArray2(self, n: int, k: int) -> List[int]:\n",
    "\n",
    "        def calculate(nums):\n",
    "            n = len(nums)\n",
    "            # print(nums)\n",
    "            num_set = set()\n",
    "            for i in range(n-1):\n",
    "                num_set.add(abs(nums[i] - nums[i+1]))\n",
    "            # print(num_set)\n",
    "            return len(num_set)\n",
    "\n",
    "        combine = list()\n",
    "        seen = set()\n",
    "        result = list()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n:\n",
    "                # print(combine)\n",
    "                if calculate(combine) == k:\n",
    "                    result = combine[::]\n",
    "                    # print(\"result\", result)\n",
    "                    return True\n",
    "                return False\n",
    "            for j in range(1, n+1):\n",
    "                if j in seen:\n",
    "                    continue\n",
    "                combine.append(j)\n",
    "                seen.add(j)\n",
    "                if dfs(i+1) is True:\n",
    "                    return True\n",
    "                combine.pop()\n",
    "                seen.remove(j)\n",
    "            return False\n",
    "        \n",
    "        t = dfs(0)\n",
    "        # print(t, result)\n",
    "        if t is True:\n",
    "            return result\n",
    "        return list()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [1]\n",
    "        mark = 1\n",
    "        for i in range(k):\n",
    "            diff = k-i\n",
    "            if mark > 0:\n",
    "                res.append(diff + res[-1])\n",
    "            else:\n",
    "                res.append(res[-1]-diff)\n",
    "            mark *= -1\n",
    "        for j in range(k+2, n+1):\n",
    "            res.append(j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [1] * n\n",
    "        diff = k\n",
    "        for i in range(1, k+1):\n",
    "            res[i] = res[i-1] + diff if i%2 else res[i-1] - diff\n",
    "            diff -= 1\n",
    "        \n",
    "        for i in range(k+1, n):\n",
    "            res[i] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = [i for i in range(1, n-k+1)]\n",
    "        left, right = n-k+1, n\n",
    "        is_right = True\n",
    "        while left <= right:\n",
    "            if is_right:\n",
    "                res.append(right)\n",
    "                right -= 1\n",
    "                is_right = False\n",
    "            else:\n",
    "                res.append(left)\n",
    "                left += 1\n",
    "                is_right = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        answer = list(range(1, n - k))\n",
    "        i, j = n - k, n\n",
    "        while i <= j:\n",
    "            answer.append(i)\n",
    "            if i != j:\n",
    "                answer.append(j)\n",
    "            i, j = i + 1, j - 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        res = list(range(1, n - k))\n",
    "        left, right = n - k, n\n",
    "        while left <= right:\n",
    "            res.append(left)\n",
    "            if right != left:\n",
    "                res.append(right)\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        List = [None]*n\n",
    "        a = 1\n",
    "        b = n\n",
    "        for i in range(0,k,2):\n",
    "            List[i] = a \n",
    "            a += 1\n",
    "        for i in range(1,k,2):\n",
    "            List[i] = b\n",
    "            b -= 1\n",
    "\n",
    "        c = List[k-1]\n",
    "\n",
    "        if k % 2 == 0:\n",
    "            for i in range(k, n):\n",
    "                List[i] = c-1\n",
    "                c -= 1\n",
    "        else:\n",
    "            for i in range(k, n):\n",
    "                List[i] = c+1\n",
    "                c += 1\n",
    "        return List\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "        # 目标排列: [1,2,...,n-k, n,n-k+1,n-1,n-k+2,...,最后一项]\n",
    "        # 思路: 前n-k个数按从小到大排列，只有 1 一种差\n",
    "        # 后k个数，按照左右指针交叉排列\n",
    "        res = [i for i in range(1, n-k+1)]\n",
    "        left, right = n-k+1, n\n",
    "        is_right = True\n",
    "        while left <= right:\n",
    "            if is_right:\n",
    "                res.append(right)\n",
    "                right -= 1\n",
    "                is_right = False\n",
    "            else:\n",
    "                res.append(left)\n",
    "                left += 1\n",
    "                is_right = True\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructArray(self, n: int, k: int) -> List[int]:\n",
    "\n",
    "        \n",
    "        half=(k+1)//2\n",
    "        list1=[]\n",
    "        \n",
    "        small=[i for i in range(1,half+1)]\n",
    "        small=small[::-1]\n",
    "        big=[i for i in range(half+1,k+2)]\n",
    "\n",
    "        for i in range(len(small)):\n",
    "            list1.append(big[i])\n",
    "            list1.append(small[i])\n",
    "        if len(big)>len(small):\n",
    "            list1.append(big[-1])\n",
    "\n",
    "        #return list1\n",
    "        \n",
    "        if n-1>k:\n",
    "            rest=[i for i in range(k+2,n+1)]\n",
    "            #return rest\n",
    "            if len(list1)==2:\n",
    "                list1=rest[::-1]+list1\n",
    "            elif len(list1)%2==0:\n",
    "                aa=list1.pop(-1)\n",
    "                list1+=rest \n",
    "                list1.append(aa)\n",
    "            else:\n",
    "                list1+=rest \n",
    "            \n",
    "            return list1 \n",
    "        \n",
    "        return list1\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
